/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  if (n === 0) return []
  const res = []
  const diff = (left, right, cur) => {
    if (left === n && right === n) {
      !res.includes(cur) && res.push(cur)
      return
    }
    if (left > right) {
      diff(left, right + 1, cur + ')')
    } else {
      let idata = null
      for (let i = 1; i <= cur.length; i++) {
        const currIData = cur.charAt(i)
        if (currIData === idata) {
          idata = currIData
          continue
        }
        idata = currIData
        const str = cur.slice(0, i) + '(' + cur.slice(i)
        diff(left + 1, right, str)
      }
    }
  }
  diff(1, 0, '(')
  return res
}
// var generateParenthesis = function (n) {
//   let res = []
//   let insertStr = (soure, start, newStr) => {
//     return soure.slice(0, start) + newStr + soure.slice(start)
//   }
//   const obj = {}
//   var fn = x => {
//     if (x == 1) {
//       obj[x] = ['()']
//       return obj[x]
//     }

//     if (obj[x]) {
//       return fn(x)
//     } else {
//       const a = fn(x - 1).reduce((pre, cur) => {
//         let b = []
//         for (let i = 0; i < cur.length; i++) {
//           b.push(insertStr(cur, i, '()'))
//         }
//         return [...pre, ...b]
//       }, [])
//       obj[x] = [...new Set(a)]
//       return obj[x]
//     }
//   }

//   return fn(n)
// }

console.log(generateParenthesis(3))
